Mining distribution change in stock order streams.

A hierarchical information theoretic technique for the discovery of non linear alternative clusterings.

A Novel Scalable Multi%2Dclass ROC for Effective Visualization and Computation.

Generation of Alternative Clusterings Using the CAMI Approach.

Logical queries over views Decidability and expressiveness.

A fast indexing approach for protein structure comparison.

is%2DrSNP a novel technique for in silico regulatory SNP detection.

MIRAGAA %2D a methodology for finding coordinated effects of microRNA expression changes and genome aberrations in cancer.



Efficient incremental mining of contrast patterns in changing data.

Enhancing the B %2Dtree by dynamic node popularity caching.

Document clustering of scientific texts using citation contexts.

A binary decision diagram based approach for mining frequent subsequences.

Classifying proteins using gapped Markov feature pairs.

Using Gene Ontology annotations in exploratory microarray clustering to understand cancer etiology.

Information theoretic measures for clusterings comparison is a correction for chance necessary%3F
Information theoretic based measures form a fundamental class of similarity measures for comparing clusterings, beside the class of pair-counting based and set-matching based measures. In this paper, we discuss the necessity of correction for chance for information theoretic based measures for clusterings comparison. We observe that the baseline for such measures, i.e. average value between random partitions of a data set, does not take on a constant value, and tends to have larger variation when the ratio between the number of data points and the number of clusters is small. This effect is similar in some other non-information theoretic based measures such as the well-known Rand Index. Assuming a hypergeometric model of randomness, we derive the analytical formula for the expected mutual information value between a pair of clusterings, and then propose the adjusted version for several popular information theoretic based measures. Some examples are given to demonstrate the need and usefulness of the adjusted measures. 1.
Using Highly Expressive Contrast Patterns for Classification %2D Is It Worthwhile%3F.

Feature Weighted SVMs Using Receiver Operating Characteristics.

Semantic Web Query Languages.
Time is omnipresent on the (Semantic) Web. However, formalism  like XML, XML Schema, RDF, OWL and (Semantic) Web query  languages have, if any, only very limited notions of temporal data types  and temporal theories built-in. Recently, the development of Web Services  for temporal operations has begun. In this article, we describe a  connection, possibly the first one, between such Web Services and Web  formalisms: A proposal of a type system for temporal and calendric data,  called multi-calendar temporal type system seamlessly integrated into a  host (query) language. The type system&#039;s associated type checking methods  are beyond the scope of this article. For proof-of-concept purposes,  the Web and Semantic Web query language Xcerpt has been chosen.
A voting approach to identify a small number of highly predictive genes using multiple classifiers.

Using graph partitioning to discover regions of correlated spatio%2Dtemporal change in evolving graphs.

Using graph partitioning to discover regions of correlated spatio%2Dtemporal change in evolving graphs.

Building more robust multi%2Dagent systems using a log%2Dbased approach.

Web Information Systems Engineering %2D WISE 2008

Mining%2C Ranking%2C and Using Acronym Patterns.

Mining influential attributes that capture class and group contrast behaviour.
Contrast data mining is a key tool for finding differences between sets of objects, or classes, and contrast patterns are a popular method for discrimination between two classes. However, such patterns can be limited in two primary ways: i) They do not readily allow second order differentiation-i.e. discovering contrasts of contrasts, ii) Mining contrast patterns often results in an overwhelming volume of output for the user. To address these limitations, this paper proposes a method which can identify contrast behaviour across both classes and also groups of classes. Furthermore, to increase interpretability for the user, it presents a new technique for finding the attributes which represent the key underlying factors behind the contrast behaviour. The associated mining task is computationally challenging and we describe an efficient algorithm to handle it, based on binary decision diagrams. Experimental results demonstrate that our technique can efficiently identify and explain contrast behaviour which would be difficult or impossible to isolate using standard techniques.
Improving k%2DNearest Neighbour Classification with Distance Functions Based on Receiver Operating Characteristics.
Abstract. The k-nearest neighbour (k-NN) technique, due to its interpretable nature, is a simple and very intuitively appealing method to address classification problems. However, choosing an appropriate distance function for k-NN can be challenging and an inferior choice can make the classifier highly vulnerable to noise in the data. In this paper, we propose a new method for determining a good distance function for k-NN. Our method is based on consideration of the area under the Receiver Operating Characteristics (ROC) curve, which is a well known method to measure the quality of binary classifiers. It computes weights for the distance function, based on ROC properties within an appropriate neighbourhood for the instances whose distance is being computed. We experimentally compare the effect of our scheme with a number of other well-known k-NN distance metrics, as well as with a range of different classifiers. Experiments show that our method can substantially boost the classification performance of the k-NN algorithm. Furthermore, in a number of cases our technique is even able to deliver better accuracy than state-of-the-art non k-NN classifiers, such as support vector machines.
g%2DMARS Protein Classification Using Gapped Markov Chains and Support Vector Machines.
Abstract. Classifying protein sequences has important applications in areas such as disease diagnosis, treatment development and drug design. In this paper we present a highly accurate classifier called the g-MARS (gapped Markov Chain with Support Vector Machine) protein classifier. It models the structure of a protein sequence by measuring the transition probabilities between pairs of amino acids. This results in a Markov chain style model for each protein sequence. Then, to capture the similarity among non-exactly matching protein sequences, we show that this model can be generalized to incorporate gaps in the Markov chain. We perform a thorough experimental study and compare g-MARS to several other state-of-the-art protein classifiers. Overall, we demonstrate that g-MARS has superior accuracy and operates efficiently on a diverse range of protein families. 1
Gene Ontology Assisted Exploratory Microarray Clustering and Its Application to Cancer.
Abstract. Gene expression profiling provides insight into the functions of genes at a molecular level. Clustering of gene expression profiles can facilitate the identification of the underlying driving biological program causing genes ’ co-expression. Standard clustering methods, grouping genes based on similar expression values, fail to capture weak expression correlations potentially causing genes in the same biological process to be grouped separately. We have developed a novel clustering algorithm which incorporates functional gene information from the Gene Ontology into the clustering process, resulting in more biologically meaningfull clusters. We have validated our method using a multi-cancer microarray dataset. In addition, we show the potential of such methods for the exploration of cancer etiology.
ROC%2Dtree A Novel Decision Tree Induction Algorithm Based on Receiver Operating Characteristics to Classify Gene Expression Data.
Gene expression information from microarray experiments is a primary form of data for biological analysis and can offer insights into disease processes and cellular behaviour. Such datasets are particularly challenging to build classifiers for, due to their very high dimensional nature and small sample size. Decision trees are a seemingly attractive technique for this domain, due to their easily interpretable white box nature and noise resistance. However, existing decision tree methods tend to perform rather poorly for classifying gene expression data. To address this gap, we introduce a new technique for building decision trees that is better suited to this scenario. Our method is based on consideration of the area under the Receiver Operating Characteristics (ROC) curve, to help determine decision tree characteristics, such as node selection and stopping criteria. We experimentally compare our algorithm, called ROCtree, against other well known decision tree techniques, on a number of gene expression datasets. The experimental results clearly demonstrate that ROC-tree can deliver better classification accuracy in a range of challenging situations.
Logical Queries over Views Decidability and Expressiveness

Discovering correlated spatio%2Dtemporal changes in evolving graphs.
Graphs provide powerful abstractions of relational data, and are widely used in fields such as network management, web page analysis and sociology. While many graph representations of data describe dynamic and time evolving relationships, most graph mining work treats graphs as static entities. Our focus in this paper is to discover regions of a graph that are evolving in a similar manner. To discover regions of correlated spatio-temporal change in graphs, we propose an algorithm called cSTAG. Whereas most clustering techniques are designed to find clusters that optimise a single distance measure, cSTAG addresses the problem of finding clusters that optimise both temporal and spatial distance measures simultaneously. We show the effectiveness of cSTAG using a quantitative analysis of accuracy on synthetic data sets, as well as demonstrating its utility on two large, real-life data sets, where one is the routing topology of the Internet, and the other is the dynamic graph of files accessed together on the 1998 World Cup official website.
Database Technologies 2007. Proceedings of the Eighteenth Australasian Database Conference

Merging Dynamic Functionality Integration of XML Transformations.

An Efficient Technique for Mining Approximately Frequent Substring Patterns.

Are Zero%2Dsuppressed Binary Decision Diagrams Good for Mining Frequent Patterns in High Dimensional Datasets%3F
Mining frequent patterns such as frequent itemsets is a core operation in many important data mining tasks, such as in association rule mining. Mining frequent itemsets in high-dimensional datasets is challenging, since the search space is exponential in the number of dimensions and the volume of patterns can be huge. Many of the state-of-the-art techniques rely upon the use of prefix trees (e.g. FPtrees) which allow nodes to be shared among common prefix paths. However, the scalability of such techniques may be limited when handling high dimensional datasets. The purpose of this paper is to analyse the behaviour of mining frequent itemsets when instead of a tree data structure, a canonical directed acyclic graph namely Zero Suppressed Binary Decision Diagram (ZBDD) is used. Due to its compactness and ability to promote node reuse, ZBDD has proven very effective in other areas of computer science, such as boolean SAT solvers. In this paper, we show how ZBDDs can be used to mine frequent itemsets (and their common varieties). We also introduce a weighted variant of ZBDD which allows a more efficient mining algorithm to be developed. We provide an experimental study concentrating on high dimensional biological datasets, and identify indicative situations where a ZBDD technology can be superior over the prefix tree based technique.
An Efficient Technique for Mining Approximately Frequent Substring Patterns.

Mining minimal distinguishing subsequence patterns with gap constraints.
Discovering contrasts between collections of data is an important task in data mining. In this paper, we introduce a new type of contrast pattern, called a Minimal Distinguishing Subsequence (MDS). An MDS is a minimal subsequence that occurs frequently in one class of sequences and infrequently in sequences of another class. It is a natural way of representing strong and succinct contrast information between two sequential datasets and can be useful in applications such as protein comparison, document comparison and building sequential classification models. Mining MDS patterns is a challenging task and is significantly different from mining contrasts between relational/transactional data. One particularly important type of constraint that can be integrated into the mining process is the maximum gap constraint. We present an efficient algorithm called ConSGapMiner, to mine all MDSs according to a maximum gap constraint. It employs highly efficient bitset and boolean operations, for powerful gap based pruning within a prefix growth framework. A performance evaluation with both sparse and dense datasets, demonstrates the scalability of ConSGapMiner and shows its ability to mine patterns from high dimensional datasets at low supports. 1.
Database Technologies 2006

Principles and Practice of Semantic Web Reasoning
XML data is often accompanied by type information, usually expressed by some schema language. Sometimes XML data can be related to ontologies defining classes of objects, such classes can also be interpreted as types. Type systems proved to be extremely useful in programming languages, for instance to automatically discover certain kinds of errors. This thesis deals with an XML query language Xcerpt, which originally has no underlying type system nor any provision for taking advantage of existing type information. We provide a type system for Xcerpt; it makes possible type inference and checking type correctness. The system is descriptive: the types associated with Xcerpt constructs are sets of data terms and approximate the semantics of the constructs. A formalism of Type Definitions is adapted to specify such sets. The formalism may be seen as a simplification and abstraction of XML schema languages. The type inference method, which is the core of this work, may be seen as abstract interpretation. A non standard way of assuring termination of fixed
Mining Generalised Emerging Patterns.

Clustering Similarity Comparison Using Density Profiles.
This paper proposes a new method for comparing clusterings both partitionally and geometrically. Our approach is motivated by the following observation: the vast majority of previous techniques for comparing clusterings are entirely partitional, i.e., they examine assignments of points in set theoretic terms after they have been partitioned. In doing so, these methods ignore the spatial layout of the data, disregarding the fact that this information is responsible for generating the clusterings to begin with. We demonstrate that this leads to a variety of failure modes. Previous comparison techniques often fail to differentiate between significant changes made in data being clustered. We formulate a new measure for comparing clusterings that combines spatial and partitional information into a single measure using optimization theory. Doing so eliminates pathological conditions in previous approaches. It also simultaneously removes common limitations, such as that each clustering must have the same number of clusters or they are over identical datasets. This approach is stable, easily implemented, and has strong intuitive appeal. spatial properties as well as their cluster membership assignments. We view a clustering as a partition of a set of points located in a space with an associated distance function. This view is natural, since popular clustering algorithms, e.g., k-means, spectral clustering, affinity propagation, etc., take as input not only a collection of points to be clustered but also a distance function on the space in which the points lie. This distance function may be specified implicitly and it may be transformed by a kernel, but it must be defined one way or another and its properties are crucial to a clustering algorithm’s output. In contrast, almost all existing clustering comparison techniques ignore the distances between points, treating clusterings as partitions of disembodied atoms. While this approach has merit under some circumstances, it seems surprising to ignore the distance func-
A Framework for Integrating XML Transformations.

A Logging%2DBased Approach for Building More Robust Multi%2Dagent Systems.

COALA A Novel Approach for the Extraction of an Alternate Clustering of High Quality and High Dissimilarity.
Cluster analysis has long been a fundamental task in data mining and machine learning. However, traditional clustering methods concentrate on producing a single solution, even though multiple alternative clusterings may exist. It is thus difficult for the user to validate whether the given solution is in fact appropriate, particularly for large and complex datasets. In this paper we explore the critical requirements for systematically finding a new clustering, given that an already known clustering is available and we also propose a novel algorithm, COALA, to discover this new clustering. Our approach is driven by two important factors; dissimilarity and quality. These are especially important for finding a new clustering which is highly informative about the underlying structure of data, but is at the same time distinctively different from the provided clustering. We undertake an experimental analysis and show that our method is able to outperform existing techniques, for both synthetic and real datasets. 1.
Discovering and Summarising Regions of Correlated Spatio%2DTemporal Change in Evolving Graphs.
Abstract — Graphs are adept at describing relational data, hence their popularity in fields including network management, webpage analysis and sociology. However, most of the current graph mining work regards graphs as static and unchanging, even though many graphs are dynamic. In this paper, we introduce a new pattern to discover from evolving graphs, namely regions of the graph that are evolving in a correlated manner. These regions of correlated spatio-temporal change group together graph changes that are topologically near (spatial) and evolve similarly (temporal) to each other. The regions can be used to summarise changes, particularly for graphs that have many simultaneous changes. We have developed an algorithm called cSTAG to summarise changes in dynamic graphs. This new algorithm discovers these regions of correlated change and identifies events that caused these changes. As a demonstration of the effectiveness of our algorithm, we applied cSTAG to summarise the changes to the Border Gateway Protocol connectivity graph during the 2005 Hurricane Katrina Disaster. cSTAG was able to identify the reported failures in Louisiana, as well as other simultaneous events. I.
Fast mining of high dimensional expressive contrast patterns using zero%2Dsuppressed binary decision diagrams.
Patterns of contrast are a very important way of comparing multidimensional datasets. Such patterns are able to capture regions of high difference between two classes of data, and are useful for human experts and the construction of classifiers. However, mining such patterns is particularly challenging when the number of dimensions is large. This paper describes a new technique for mining several varieties of contrast pattern, based on the use of Zero-Suppressed Binary Decision Diagrams (ZBDDs), a powerful data structure for manipulating sparse data. We study the mining of both simple contrast patterns, such as emerging patterns, and more novel and complex contrasts, which we call disjunctive emerging patterns. A performance study demonstrates our ZBDD technique is highly scalable, substantially improves on state of the art mining for emerging patterns and can be effective for discovering complex contrasts from datasets with thousands of attributes.
Mining Minimal Contrast Subgraph Patterns.
In this paper, we introduce a new type of contrast pattern, the minimal contrast subgraph. It is able to capture structural differences between any two collections of graphs and can be useful in chemical compound comparison and building graph classification models. However, mining minimal contrast subgraphs is a challenging task, due to the exponentially large search space and graph (sub)isomorphism problems. We present an algorithm which utilises a backtracking tree to first compute the maximal common edge sets and then uses a minimal hypergraph transversal algorithm, to derive the set of minimal contrast subgraphs. An experimental evaluation demonstrates the potential of our technique for finding interesting differences in graph data.
Grid Security Framework for Managing the Certificate.

XSLTGen A System for Automatically Generating XML Transformations Via Semantic Mappings.
Abstract. XML is rapidly emerging as a dominant standard for representing and exchanging information. The ability to transform and present data in XML is crucial and XSLT is a relatively recent programming language, specially designed to support this activity. Despite its utility, however, XSLT is widely considered a difficult language to learn. In this paper, we present a novel system called XSLTGen, an automatic XSLT Generator. This system automatically generates an XSLT stylesheet, given a source XML document and a desired output HTML or XML document. It allows users to become familiar with and learn XSLT stylesheets, based solely on their knowledge of XML or HTML. Our method for automatically generating XSLT transformations is based on the use of semantic mappings between the input and output documents. We show how such mappings can be first discovered and then employed to create XSLT stylesheets. The results of our experiments show that XSLTGen works well with a number of different varieties of XML and HTML documents. 1
Transformation and Reaction Rules for Data on the Web.
The transformation and manipulation of XML is an increasingly important research topic. This paper examines a number of issues with regard to languages for transforming and reacting to changes on XML data. On the transformation side, we focus on XSLT, a powerful language for converting XML data into other formats. We look at analysis and optimisation issues for XSLT, as well as support for debugging and automatic generation. On the reactivity side, we focus on an event-condition-action rule approach, which is a natural candidate for the support of reactive functionality on XML repositories. Keywords: XML, XSLT, active rules  1 
Mining Minimal Distinguishing Subsequence Patterns with Gap Constraints.
Discovering contrasts between collections of data is an important task in data mining. In this paper, we introduce a new type of contrast pattern, called a Minimal Distinguishing Subsequence (MDS). An MDS is a minimal subsequence that occurs frequently in one class of sequences and infrequently in sequences of another class. It is a natural way of representing strong and succinct contrast information between two sequential datasets and can be useful in applications such as protein comparison, document comparison and building sequential classification models. Mining MDS patterns is a challenging task and is significantly different from mining contrasts between relational/transactional data. One particularly important type of constraint that can be integrated into the mining process is the maximum gap constraint. We present an efficient algorithm called ConSGapMiner, to mine all MDSs according to a maximum gap constraint. It employs highly efficient bitset and boolean operations, for powerful gap based pruning within a prefix growth framework. A performance evaluation with both sparse and dense datasets, demonstrates the scalability of ConSGapMiner and shows its ability to mine patterns from high dimensional datasets at low supports. 1.
Discovery of Minimal Unsatisfiable Subsets of Constraints Using Hitting Set Dualization.
Abstract. An unsatisfiable set of constraints is minimal if all its (strict) subsets are satisfiable. The task of type error diagnosis requires finding all minimal unsatisfiable subsets of a given set of constraints (representing an error), in order to generate the best explanation of the error. Similarly circuit error diagnosis requires finding all minimal unsatisfiable subsets in order to make minimal diagnoses. In this paper we present a new approach for efficiently determining all minimal unsatisfiable sets for any kind of constraints. Our approach makes use of the duality that exists between minimal unsatisfiable constraint sets and maximal satisfiable constraint sets. We show how to incrementally compute both these sets, using the fact that the complements of the maximal satisfiable constraint sets are the hitting sets of the minimal unsatisfiable constraint sets. We experimentally compare our technique to the best known method on a number of large type problems and show that considerable improvements in running time are obtained.
Web and Semantic Web Query Languages A Survey.

Flavours of XChange%2C a Rule%2DBased Reactive Language for the %28Semantic%29 Web.
Abstract. This article introduces XChange, a rule-based reactive language for the (Semantic) Web. Stressing application scenarios, it first argues that high-level reactive languages are needed for both Web and Semantic Web applications. Then, it discusses technologies and paradigms relevant to high-level reactive languages for the (Semantic) Web. 1
Optimization of XSLT by Compact Specialization and Combination.

Composite event queries for reactivity on the web.
Reactivity on the Web is an emerging issue. The capability to automatically react to events (such as updates to Web resources) is essential for both Web services and Semantic Web systems. Such systems need to have the capability to detect and react to complex, real life situations. This presentation gives flavours of the high-level language XChange, for programming reactive behaviour on the Web.
Static Analysis of XSLT Programs.

Managing Semantic Compensation in a Multi%2Dagent System.
Abstract. Recovery in agent systems is an important and complex problem. This paper describes an approach to improving the robustness of an agent system by augmenting its failure-handling capabilities. The approach is based on the concept of semantic compensation: “cleaning up ” failed or canceled tasks can help agents behave more robustly and predictably at both an individual and system level. However, in complex and dynamic domains it is difficult to define useful specific compensations ahead of time. This paper presents an approach to defining semantic compensations abstractly, then implementing them in a situationspecific manner at time of failure. The paper describes a methodology for decoupling failure-handling from normative agent logic so that the semantic compensation knowledge can be applied in a predictable and consistent way – with respect to both individual agent reaction to failure, and handling failure-related interactions between agents – without requiring the agent application designer to implement the details of the failure-handling model. In particular, in a multi-agent system, robust handling of compensations for delegated tasks requires flexible protocols to support management of compensation-related activities. The ability to decouple the failure-handling conversations allows these protocols to be developed independently of the agent application logic. 1
XSLTGen A System for Automatically Generating XML Transformations via Semantic Mappings.
Abstract. XML is rapidly emerging as a dominant standard for representing and exchanging information. The ability to transform and present data in XML is crucial and XSLT is a relatively recent programming language, specially designed to support this activity. Despite its utility, however, XSLT is widely considered a difficult language to learn. In this paper, we present a novel system called XSLTGen, an automatic XSLT Generator. This system automatically generates an XSLT stylesheet, given a source XML document and a desired output HTML or XML document. It allows users to become familiar with and learn XSLT stylesheets, based solely on their knowledge of XML or HTML. Our method for automatically generating XSLT transformations is based on the use of semantic mappings between the input and output documents. We show how such mappings can be first discovered and then employed to create XSLT stylesheets. The results of our experiments show that XSLTGen works well with a number of different varieties of XML and HTML documents. 1
ParaDualMiner An Efficient Parallel Implementation of the DualMiner Algorithm.
Abstract. Constraint based mining finds all itemsets that satisfy a set of predicates. Many constraints can be categorised as being either monotone or antimonotone. Dualminer was the first algorithm that could utilise both classes of constraint simultaneously to prune the search space. In this paper, we present two parallel versions of DualMiner. The ParaDualMiner with Simultaneous Pruning efficiently distributes the task of expensive predicate checking among processors with minimum communication overhead. The ParaDualMiner with Random Polling makes further improvements by employing a dynamic subalgebra partitioning scheme and a better communication mechanism. Our experimental results indicate that both algorithms exhibit excellent scalability. 1
Optimization of XML Transformations Using Template Specialization.
Abstract. XSLT is the primary language for transforming and presenting XML. Effective optimization techniques for XSLT are particularly important for applications which involve high volumes of data, such as online server-side processing. This paper presents a new approach for optimizing XSLT transformations, based on the notion of template specialization. We describe a number of template specialization techniques, suitable for varying XSLT design styles and show how such specializations can be used at run time, according to user input queries. An experimental evaluation of our method is undertaken and it is shown to be particularly effective for cases with very large XML input. 1
An Event%2DCondition%2DAction Language for XML.
ECA rules automatically perform actions in response to events provided that stated conditions hold. They are used in conventional data warehouses for incremental maintenance of materialised views, validation and cleansing of data, and maintaining audit trails. By analogy, ECA rules could also be used as an integrating technology for providing this kind of functionality on XML repositories. Further potential uses include checking key and other constraints on XML documents, and performing automatic repairs when violations of constraints are detected. In a `push &#039; type environment, they can be used for automatically broadcasting information to subscribers as the contents
On the decidability of the termination problem of active database systems.

Discovery of Emerging Patterns and Their Use in Classification.

A Fast Algorithm for Computing Hypergraph Transversals and its Application in Mining Emerging Patterns.
Abstract Computing the minimal transversals of a hypergraph isan important problem in computer science that has significant applications in data mining. In this paper, we present anew algorithm for computing hypergraph transversals and highlight their close connection to an important class ofpatterns known as emerging patterns. We evaluate our technique on a number of large datasets and show that it out-performs previous approaches by a factor of 9-29 times. Introduction Analysis of hypergraphs is an importantproblem in discrete mathematics which has many applications in computer science. Example areas range from min-imal diagnosis and propositional circumscription [10], to learning boolean formulae [2], and boolean switching the-ory [4]. The hypergraph minimal transversal problem is particu-larly significant from a data mining perspective. Indeed, the algorithmic complexity of mining maximal frequent item-sets and minimal infrequent itemsets is closely linked to the complexity of computing minimal hypergraph transversals[6].
Classification Using Constrained Emerging Patterns.

CodeX An Approach for Debugging XSLT Transformations.

Fast Algorithms for Mining Emerging Patterns.

An event%2Dcondition%2Daction language for XML.
ECA rules automatically perform actions in response to events provided that stated conditions hold. They are used in conventional data warehouses for incremental maintenance of materialised views, validation and cleansing of data, and maintaining audit trails. By analogy, ECA rules could also be used as an integrating technology for providing this kind of functionality on XML repositories. Further potential uses include checking key and other constraints on XML documents, and performing automatic repairs when violations of constraints are detected. In a `push &#039; type environment, they can be used for automatically broadcasting information to subscribers as the contents
Analysis and optimisation of event%2Dcondition%2Daction rules on XML.
XML is a now a dominant standard for storing and exchanging information. With its increasing use in areas such asdatawarehousing and e-commerce, there is a rapidly growing need for rule-based technology to support reactive functionality on XML repositories. Eventcondition-action (ECA) rules automatically perform actions in response to events and are a natural facility to support such functionality. In this paper, we study ECA rules in the context of XML data. We de ne a simple language for specifying ECA rules on XML repositories. The language is illustrated by means of some examples, and its syntax and semantics are then speci ed more formally. We theninvestigate methods for analysing and optimising these ECA rules, a task which has added complexity in this XML setting compared with conventional active databases. 1
Optimising Active Database Rules by Partial Evaluation and Abstract Interpretation.
Active databases provide reactive functionality by supporting event-condition-action rules of the form `on event if condition do actions&#039;. Akey issue for active databases is optimising the run-time execution of such rules. Given the data-intensive nature of the rules, previous research has aimed at either adopting existing database optimisation techniques, or developing special-purpose solutions for improving execution
Expressiveness Issues and Decision Problems for Active Database Event Queries.
. A key facility of active database management systems is their  ability to detect and react to the occurrence of events. Such events can  be either atomic in nature, or specified using an event algebra to form  complex events. An important role of an event algebra is to define the  semantics of when events become invalid (event consumption). In this  paper, we examine a simple event algebra and provide a logical framework  for specification of various consumption policies. We then study the  problems of equivalence and implication, identifying a powerful class of  complex events for which equivalence is decidable. We then demonstrate  how extensions of this class lead to undecidability.  1 

Transaction Oriented Computational Models for Multi%2DAgent Systems.
BDI (Belief, Desire, Intention) is a mature and commonly adopted architecture  for Intelligent Agents. However, the current computational model adopted  by BDI has a number of problems with concurrency control, recoverability and  predictability. This has hindered the construction of agents having robust and predictable  behaviour. Indeed the conceptual and practical tools needed for building  dependable agent systems, resilient to faults and other unexpected situations, are  still at an early stage of research.
A Dynamic Approach to Termination Analysis for Active Database Rules.
. An important behavioural property for sets of active database  rules is that of termination. In current commercial database systems, termination  is guaranteed by imposing a fixed upper limit on the number  of recursive rule firings that may occur. This can have undesirable effects  such as prematurely halting correct executions. We describe a new  approach based on a dynamic upper limit to the number of rule firings.  This limit reflects knowledge about past rule behaviour on the database  and provides a more accurate measure for when the DBMS should terminate  rule execution. The approach incurs little cost and can easily be  integrated with current techniques for static analysis of active rules.  1 Introduction  Active databases provide the functionality of traditional databases and additionally are capable of reacting automatically to state changes without user intervention. This is achieved by means of Event-Condition-Action (ECA) rules of the form on event if condition do actio...

Decidability of First%2DOrder Logic Queries over Views.
. We study the problem of deciding satisfiability of first order logic queries over views, our aim being to delimit the boundary between the decidable and the undecidable fragments of this language. Views currently occupy a central place in database research, due to their role in applications such as information integration and data warehousing. Our principal result is the identification of an important decidable class of queries over unary conjunctive views. This extends the decidability of the classical class of first order sentences over unary relations (the Lowenheim class). We then demonstrate how extending this class leads to undecidability. In addition to new areas, our work also has relevance to extensions of results for related problems such as query containment, trigger termination, implication of dependencies and reasoning in description logics. Key words: satisfiability, decidability, first order logic, database queries, database views, conjunctive queries, unary views, ine...
Abstract Interpretation for Termination Analysis in Functional Active Databases.

Decidability and Undecidability Results for the Termination Problem of Active Database Rules.
Active database systems enhance the functionality of traditional databases through the use of active rules or `triggers&#039;. One of the principal questions for such systems is that of termination - is it possible for the rules to recursively activate one another indefinitely, given an initial triggering event. In this paper, we study the decidability of the termination problem, our aim being to delimit the boundary between the decidable and the undecidable. We present two families of rule languages, the one literal languages where each update is permitted to have just one atom in its body, and the unary languages where only unary relations may be updated, but higher arity relations may be accessed through views. Within each of these, we identify members close to the boundary of (un)decidability. Our context is similar to the while query language and the dynamics gives an interesting contrast to Datalog with negation; our results shed insights on the power of triggers as well as comparison of the termination problem to boundedness and query containment.
Incremental View Maintenance By Base Relation Tagging in Distributed Databases.
. The incremental view maintenance problem deals with the efficient updating of materialized views in response to updates to base relations. This paper considers the problem in a distributed database environment, with communication cost minimization as the primary objective. The views considered are defined based on the relational join operation. The approach is to use &#034;yes&#034;/&#034;no&#034; tags as auxiliary data on tuples in the base relations to indicate whether the tuples participate in joins. These tags will help avoid sending irrelevant data over the network and thus reduce the communication cost. Two basic view maintenance algorithms are proposed using the tags. In addition to reducing communication costs, an important feature of these two basic algorithms is that they derive the &#034;exact change&#034; to views without looking at the old views. This feature allows us to maintain certain aggregates on views without actually materializing the views themselves; this feature is useful in applications s...
Abstract Interpretation of Active Rules and its Use in Termination Analysis.

Structural Issues in Active Rule Systems.
Active database systems enhance the functionality of traditional databases through the use of active rules or `triggers&#039;. There is little consensus, though, on what components should be included in a rule system. In this paper, the expressive power of some simple active database rule systems is examined and the effect of choosing different features studied. Four important parameters of variation are presented, namely the rule language, the external query language, the meta rule language and the pending rule structure. We show that each of these is highly influential in determining the expressiveness of the rule system as a whole, and that an appreciation of them can serve as a basis for understanding the broader picture of system behaviour.
Issues in Active Databases.

Active Databases and Agent Systems %2D A Comparison.
This paper examines Active Databases and Agent Systems, comparing their purpose, structure, functionality, and implementation. Our presentation is aimed primarily at an audience familiar with active database technology. We show that they draw upon very similar paradigms in their quest to supply reactivity. This presents opportunities for migration of techniques and formalisms between the two fields. 1 fjbailey,kemp,dnk,raog@cs.mu.oz.au 2 georgeff@aaii.oz.au 3 Appears in T.Sellis, editor, Proceedings of the Second International Workshop on Rules in Database Systems, Lecture Notes in Computer Science 985, pages 342-356, Athens, Greece, 1995. 1 Introduction In recent times, two technologies have become prominent in the database and artificial intelligence research communities. An Active Database (ADB) is a system which supplements traditional database functionality by reacting automatically to state changes, both internal and external, without user intervention. An Agent System (A...
